
// 方案二：原地更新
// 时间复杂度：O(mn)
// 空间复杂度：O(1)
var gameOfLife = function(board) {
    const directions = [
                        [-1, 0],
                        [1, 0],
                        [0, -1],
                        [0, 1],
                        [-1, -1],
                        [-1, 1],
                        [1, -1],
                        [1, 1]
                    ];

    const m = board.length
    const n = board[0].length

    // 遍历每个细胞，并确定它最终的状态
    for (let row = 0; row < m; row++) {
        for (let col = 0; col < n; col++) {
            // 对于每一个细胞统计其八个相邻位置里的活细胞数量
            let liveNeighbors = 0
            for (let dir of directions) {
                const nextRow = row + dir[0]
                const nextCol = col + dir[1]
                if (nextRow < m && nextCol < n && nextRow >= 0 && nextCol >= 0) {
                    if (Math.abs(board[nextRow][nextCol]) == 1) liveNeighbors++
                }
            }
            // 1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
            if (board[row][col] == 1 && (liveNeighbors < 2 || liveNeighbors > 3))
                board[row][col] = -1
            // 2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；

            // 3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；

            // 4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
            if (board[row][col] == 0 && liveNeighbors == 3) board[row][col] = 2
        }
    }

    // 遍历 board 得到一次更新后的状态
    for (let row = 0; row < m; row++) {
        for (let col = 0; col < n; col++) {
            if (board[row][col] > 0) {
                board[row][col] = 1
            } else {
                board[row][col] = 0
            }
        }
    }
};

// 方案一：使用辅助数组
// 时间复杂度：O(mn)
// 空间复杂度：O(mn)
var gameOfLife1 = function(board) {
    const directions = [
                        [-1, 0],
                        [1, 0],
                        [0, -1],
                        [0, 1],
                        [-1, -1],
                        [-1, 1],
                        [1, -1],
                        [1, 1]
                    ];

    const m = board.length
    const n = board[0].length
    // 创建复制数组 copyBoard
    const copyBoard = new Array(m).fill().map(() => new Array(n).fill(0))
    // 从原数组复制一份到 copyBoard 中
    for (let row = 0; row < m; row++) {
        for (let col = 0; col < n; col++) {
            copyBoard[row][col] = board[row][col]
        }
    }
    // 遍历每个细胞，并确定它最终的状态
    for (let row = 0; row < m; row++) {
        for (let col = 0; col < n; col++) {
            // 对于每一个细胞统计其八个相邻位置里的活细胞数量
            let liveNeighbors = 0
            for (let dir of directions) {
                const nextRow = row + dir[0]
                const nextCol = col + dir[1]
                if (nextRow < m && nextCol < n && nextRow >= 0 && nextCol >= 0) {
                    if (copyBoard[nextRow][nextCol] == 1) liveNeighbors++
                }
            }
            // 1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
            if (copyBoard[row][col] == 1 && (liveNeighbors < 2 || liveNeighbors > 3))
                board[row][col] = 0
            // 2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；

            // 3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；

            // 4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
            if (copyBoard[row][col] == 0 && liveNeighbors == 3) board[row][col] = 1
        }
    }
};